FIG. 1 is a block diagram illustrating a turbo-encoder.
If two recursive symmetric convolution (RSC) codes are parallel-concatenated by an interleaver, the turbo-code (TC) is formed. In more detail, turbo code can be formed by combining a parity bit (Y1) generated by encoding an input data (X) of the turbo-encoder shown in FIG. 1 by a first RSC construction encoder (ENC1) 101 and the other parity bit (Y2) generated by encoding the input data (X) by a second RSC construction encoder (ENC2) 103.
The longer the minimum hamming distance (MHD), the higher the turbo-code (TC) performance. The MHD may be denoted by the number of bits having different information at neighboring positions among individual sequences.
Generally, if a sequence “000 . . . ” is used as a reference sequence, the MHD may be denoted by the number of bits different from the reference sequence. As a result, the MHD may be denoted by the number of weights (i.e., the number of “1”) contained in individual sequences. Therefore, the MHD performance is affected by a specific action which prevents the same information from being located at the neighboring positions of sequences applied to the first and second RSC construction encoders 101 and 103. This performance is under the control of the interleaver 102.
FIG. 1 exemplarily shows an interleaver based on a regular rectangular permutation. The interleaver of FIG. 1 applies an appropriate permutation to a sequence of the length “k”, records the resultant sequence in a row direction of a rectangular matrix of M×N bits, and reads the recorded sequence in the column direction.
A detailed description of the interleaver shown in FIG. 1 is shown in FIG. 2.
FIG. 2 exemplarily shows a method for performing a regular permutation (RP).
The RP method of FIG. 2 writes a sequence in the row direction according to the above-mentioned regular rectangular permutation (RRP), reads the sequence in the column direction, and outputs the resultant sequence. For the convenience of description, the numbers written in the matrix in FIG. 2 are equal to the index (i) of the input sequence.
Generally, the relationship between the index of the input sequence in the RP and the other index (j) of the output sequence can be represented by the following equation 1, so that the index (i) and the other index (j) can be mapped to each other by Equation 1:i=Π(j)=P·j[mod K]  [Equation 1]
In Equation 1, “K” is the size of the interleaver. “P” and “K” are mutually-disjointed integers, and correspond to the numbers of columns of FIG. 2. Based on the above-mentioned mapping relationship, FIG. 2 shows the index mapping process executed by i=Π(j)=7·j[mod 32] under K=32 and P=7.
The input sequence (I) having the length of 32 bits is recorded in the row direction according to the above-mentioned index mapping relationship, and is then read in the column direction, so that it is changed to an output sequence (I′).
In the meantime, the RSC sequence may include a RTZ (Return-To-Zero) sequence which reduces the weight of a codeword. The RTZ sequence enables the construction encoder to output a specific sequence in which the value “0” is repeated, so that the weight of the output sequence is decreased.
In more detail, as shown in FIG. 1, provided that the input sequence of the first RSC construction encoder 101 is set to a sequence (I), and a predetermined RTZ sequence exists in the sequence (I), the weight of the parity bit (Y1) created by the first RSC construction encoder 101 becomes lower.
A sequence interleaved by the interleaver 102 is applied to the second RSC construction encoder 103. If this sequence received in the second RSC construction encoder 103 is called a sequence (I′), and the interleaved sequence (I′) also includes the RTZ sequence, the weight of the parity bit (Y2) created by the second RSC construction encoder 103 becomes lower, so that the MHD of the whole codeword becomes lower. Therefore, the interleaver 102 must be designed not to generate the RTZ sequence in the sequence (I′) received in the second RSC construction encoder 103.
FIG. 3A shows an example of the RTZ (Return-To-Zero) sequence having the weight “2”. FIG. 3B shows an example of the RTZ (Return-To-Zero) sequence having the weight “3”. FIG. 3C shows an example of the RTZ (Return-To-Zero) sequence having the weights “6” and “9”.
In more detail, the RTZ sequence having the weight “2” is shown in FIG. 3A. Referring to FIG. 3A, the input sequence (I) includes the RTZ sequence in which the bit “1” is spaced apart from the other bit “1” by a predetermined distance corresponding to 7 bits. And, FIG. 3A shows the interleaving based on the above-mentioned regular rectangular permutation (RRP) in which the input sequence (I) is recorded in the row direction and is then read in the column direction.
In the case of the RTZ sequence having the weight “2” as shown in FIG. 3A, the MHD (dmin) can be represented by the following equation 2:dmin≅7M/2  [Equation 2]
In Equation 2, the number “7” is 7 bits indicating to the distance between two “1” values in the input sequence (I), M is the number of rows in the M×N matrix, and the number “2” is the number of the values “1” indicating the last bits of individual sequences. As can be seen from FIG. 3A, the MHD (dmin) gets closer to “7M/2”.
FIG. 3B shows an example of the RTZ (Return-To-Zero) sequence having the weight “3”. In more detail, FIG. 3B shows an example of the RTZ (Return-To-Zero) sequence in which three “1” values (e.g., . . . 1101 . . . ) are arranged in the input sequence (I).
In the case of the RTZ sequence having the weight “3” as shown in FIG. 3B, the MHD (dmin) can be represented by the following equation 3:dmin≅3M/2  [Equation 3]
In Equation 3, the number “3” is 3 bits indicating to the distance between the last bits “1” in the input sequence (I), M is the number of rows in the matrix, and the number “2” is the number of the values “1” indicating the last bits of individual sequences. As can be seen from FIG. 3B, the MHD (dmin) gets closer to “3M/2”.
In the case of applying the regular permutation (RP) to the RTZ sequence in FIGS. 3A and 3B, the longer the length “K” of a total sequence, the higher the value (dmin), thereby preventing the RTZ sequence from being contained in the output sequence (I).
In the meantime, FIG. 3C exemplarily shows the RTZ sequence having the weights “6” and “9”. In the case of this RTZ sequence of FIG. 3C, the MHD cannot be generally defined, and varies with a specific pattern of the corresponding sequence.
The input sequence (I) of FIG. 3C includes the RTZ sequence ( . . . 1101 . . . ) in the input sequence arranged in the column direction, and includes the other RTZ sequence ( . . . 100001 . . . ) in the output sequence arranged in the row direction.
If the RTZ sequence is contained in the input sequence (I) having the weights “6” and “9” by the interleaving based on the RP, it can be recognized that the performance that the RTZ sequence is not contained in the output sequence (I) may be deteriorated.
Therefore, there has been widely used an almost regular permutation (ARP) causing the disorder while the RTZ sequence is read in the column direction of the interleaver memory matrix. The ARP can maintain the RP characteristics having a good performance associated with the other RTZ sequence of FIG. 3A or 3B, and can prevent the RTZ sequence of FIG. 3C from being generated.
In brief, the ARP is acquired by adding fluctuation vectors to the RP. In more detail, the above-mentioned RP cannot avoid the RTZ sequence having the weight “6” or “9” in the interleaving process. In order to prevent the RTZ sequence having the weight “6” or “9” from being generated in the interleaving process, the disorder must be encountered in the RP, so that the above-mentioned fluctuation vectors are added to the RP to encounter the disorder in the RP.
Presently, the ARP has been widely used as a turbo-code interleaver of DVB-RCS, DVB-RCT, and IEEE 802.16. A variety of applications of the above-mentioned ARP have been described in “ETSI EN 301 790 v1.2.2(2000-12)” and “Draft IEEE standard Local and Metropolitan area networks, Part 16”.
FIG. 4 is a conceptual diagram illustrating the almost regular permutation (ARP) based on the fluctuation vectors.
The ARP can be represented by the following index mapping relationship of Equation 4, so that it can encounter the disorder in the recording/reading process by adding the fluctuation vectors to the RP using the following Equation 4:i=Π(j)=P·j+Q(j)mod K  [Equation 4]
In Equation 4, Q(j) is indicative of the fluctuation vector. And, the fluctuation vector Q(j) can also be represented by the following equation 5:Q(j)=A(j)·P+B(j)=C(α(j)·P+β(j))  [Equation 5]
In Equation 5, “C” is indicative of a disorder period, “A(j)” or “B(j)” is indicative of a periodic function having the period (C), and “P” is equal to or less than 20% of the value “K/P”. Also, “Q(0)” may be set to “0”, and the ARP can be defined by both “2(C−1)” number of integers (i.e., 2(C−1) integers) defining the values A(j) and B(j) and the value “P”.
FIG. 4 shows a variety of processes encountered while the sequence is recorded or read by the above-mentioned fluctuation vector. Detailed description of the encountered processes has been disclosed in “Designing Good Permutations for Turbo-codes: Towards a Single Model” written by C. Berrou, and Y. Saouter et al.
In order to reduce the number of interleaver parameters defining the above-mentioned ARP, a specific ARP capable of satisfying the following conditions 1), 2), and 3) can be proposed as follows:
1) the ARP must apply a single value, which is set to any one of the remaining values other than “0”;
2) A(j)′ and B(j)′ exist in the ARP, in which each of A(j)′ and B(j)′ is a multiple of “C”; and
3) α(j) and β(j) are integers between “0” and “8”, and each of α(j) and β(j) is set to a multiple of “C”.
A detailed application example of the above-mentioned ARP is as follows.
In more detail, the left part of FIG. 5 shows the index mapping relationship based on the RP satisfying P=7 and K=32 in the same manner as in FIG. 2, and the right part of FIG. 5 shows that the mapping relationship based on the above-mentioned RP is represented by the fluctuation vector Q(j) as shown in FIG. 6.i=Π(j)=P·j+Q(j)mod K=7·j+Q(j)mod 32  [Equation 6]
In Equation 6, Q(j) can be represented by the following Equation 7:
                                                                        Q                ⁡                                  (                  j                  )                                            =                            ⁢                              C                ⁡                                  (                                                                                    α                        ⁡                                                  (                          j                          )                                                                    ·                      P                                        +                                          β                      ⁡                                              (                        j                        )                                                                              )                                                                                                        =                            ⁢                              {                                                                                                                              0                          ,                                                ⁢                                                                                                                                                                                                                if                          ⁢                                                                                                          ⁢                          j                                                =                                                  0                          ⁢                                                                                                          ⁢                          mod                          ⁢                                                                                                          ⁢                          4                                                                                                                                                                                                                              4                            ·                            1                                                    ,                                                ⁢                                                                                                                                                                                                                if                          ⁢                                                                                                          ⁢                          j                                                =                                                  1                          ⁢                                                                                                          ⁢                          mod                          ⁢                                                                                                          ⁢                          4                                                                                                                                                                                                                              4                            ·                            1                            ·                            7                                                    +                                                      4                            ·                            3                                                                          ,                                                                                                                                      if                          ⁢                                                                                                          ⁢                          j                                                =                                                  2                          ⁢                                                                                                          ⁢                          mod                          ⁢                                                                                                          ⁢                          4                                                                                                                                                                                                                              4                            ·                            1                            ·                            7                                                    +                                                      4                            ·                            4                                                                          ,                                                                                                                                      if                          ⁢                                                                                                          ⁢                          j                                                =                                                  3                          ⁢                                                                                                          ⁢                          mod                          ⁢                                                                                                          ⁢                          4                                                                                                                                                                            [                  Equation          ⁢                                          ⁢          7                ]            
In the case of the disorder encountered in a first-column directional mapping process in the RP index mapping relationship shown in the left side of FIG. 5, j=0 is mapped to i=0, j=1 is mapped to i=11 instead of i=7, j=2 is mapped to i=22 instead of i=14, and j=3 is mapped to i=1 instead of i=21, as shown in the right side of FIG. 5.
However, the above-mentioned fluctuation vector Q(j) is a function having the period “C”, so that the interleaver size “K” (i.e., the length “K” of the interleaving information) must be set to a multiple of “C”. In other words, the above-mentioned example in which the period C is set to “4” can provide only the interleaver having the length denoted by a multiple of “4”, so that there is needed an improved technology capable of providing the interleaver having a continuous length simultaneously while using the ARP.